package q46_permute;

import java.util.ArrayList;
import java.util.List;


public class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> res = new ArrayList<>();


    public List<List<Integer>> permute(int[] nums) {

        boolean[] used = new boolean[nums.length];
        dfs(nums, used);
        return res;
    }

    /**
     * 全排列存在一些特殊的地方
     * 1 我们不需要在参数中加入index，因为我们每次都要从0开始遍历数组来找能够加入排列的数字
     * 2 我们需要加入一个used数组作为参数来记录每次用过了哪些数字，接下来要用的数只能够在剩下的数字里面拿
     */
    private void dfs(int[] nums, boolean[] used) {
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path));
        }

        // 注意 这里的i每次都要从0开始 所以不需要index了
        for (int i = 0; i < nums.length; i++) {
            // 数字没有用过才能够继续 用过的数字则不能再使用
            if (!used[i]) {
                used[i] = true;
                path.add(nums[i]);
                dfs(nums, used);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.permute(new int[]{1,2,3}));
    }


}
